#include "ListNode.h"

class ReverseBetween {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == nullptr || m > n) {
            return head;
        }

        ListNode* p = head;
        ListNode* m_pre = nullptr;//m位置的前一个节点
        ListNode* n_end = nullptr;//n位置节点
        for (int i = 0; i < n; ++i) {
            if (i == m-2) {
                m_pre = p;
            }
            if (i == n-1) {
                n_end = p;
            }
            p = p->next;
        }
        ListNode* n_next = n_end->next;//n位置的后一个节点
        n_end->next = nullptr;
        if (m_pre == nullptr) {
            ListNode* new_bet = reverse(head);
            getTail(new_bet)->next = n_next;
            return new_bet;
        }
        ListNode* new_bet = reverse(m_pre->next);
        getTail(new_bet)->next = n_next;
        m_pre->next = new_bet;
        return head;
    }

    ListNode* reverse(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* pre = nullptr;
        while (head) {
            ListNode* next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    ListNode* getTail(ListNode* head) {
        ListNode* p = head;
        while (p && p->next) {
            p = p->next;
        }
        return p;
    }
};